package leetcode_day._2021._202103;

import java.util.ArrayDeque;

/**
 * @author yzh
 * @data 2021/3/24 18:49
 * 132 模式
 * i < j < k ，nums[i] < nums[k] < nums[j]
 * 思路：
 * 直接三层循环
 * 单调栈
 */
public class _24_456 {
    public static void main(String[] args) {
        System.out.println(new _24_456().find132pattern(new int[]{3, 2, 1, 2}));
    }

    // 超时
    public boolean find132pattern_first(int[] nums) {
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                if (nums[j] > nums[i]) {
                    for (int k = j + 1; k < nums.length; k++) {
                        if (nums[k] < nums[j] && nums[k] > nums[i]) return true;
                    }
                }
            }
        }
        return false;
    }

    /**
     * 单调栈
     * 从后往前遍历，栈中的元素是最大的
     * 如果数组中的数比栈中的数大，那么就把大的数放入栈中，然后跟 k 值比较，如果比 k 大，
     * 则把这个数赋值给 k
     */
    public boolean find132pattern(int[] nums) {
        if (nums == null || nums.length < 3) return false;
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        int k = Integer.MIN_VALUE;
        for (int i = nums.length - 1; i >= 0; --i) {
            if (nums[i] < k) return true;
            while (!stack.isEmpty() && nums[i] > stack.peekLast()) k = Math.max(k, stack.pollLast());
            stack.addLast(nums[i]);
        }
        return false;
    }
}
